On va procéder par récurrence \(\to\) l'initialisation est facile.

Pour l'hérédité, on utilise l'hypothèse de récurrence en passant par la probabilité conditionnelle.

Si \((*)\) est vraie, alors on peut retrouver \(Q(x_n,y)\) via les probabilités conditionnelles, ce qui donne une caractérisation.

On développe l'espérance via une somme d'indicatrices.

On a le résultat en passant aux Transitions.w

On a le résultat en passant par la proba conditionnelle et la formule avec le produit.

On simplifie en utilisant \(2)\).

On retrouve alors la formule avec le produit, qui est une caractérisation d'une chaîne de Marov.

On veut montrer que la connaissance du présent seule est importante dans la connaissance du passé \(\to\) pour cela, on conditionne par des événements \(\{X_i=x_i\}\) de probabilité non nulle.

On peut tout simplifier en passant par le caractère iid des \(U_i\) \(\to\) cela donne la propriété de Markov et la transition.

C'est une matrice \(2\times 2\).

Pour la formule de récurrence, on passe par les probabilités totales.

On peut alors calculer le terme général de cette Suite arithmético-géométrique.

On peut alors calculer \(Q^n\), en changent les valeurs de \(p_0\) et en passant à \(1-p_n\) pour certains coefficients.

On cherche la limite de la suite \((p_n)_n\) (qui est arithmético-géométrique).

On a donc la loi limite, via des masses de Dirac.

Cela se montre rapidement via l'expression.

On peut calculer \({\Bbb P}(T=k|X_0=1)\) en passant par un produit de coefficients de la matrice.

Attention au cas particulier qui n'est pas couvert par la formule.

On calcule ensuite l'espérance en sommant (série géométrique).

On calcule cela via une somme de toutes les possibilités.

On va passer par la définition \({\Bbb P}_0(H_0=\infty)=0\).

On commence par calculer \({\Bbb P}_0(H_0\gt n)\), ce qui se fait rapidement via les propriétés de cette chaîne.

On peut passer à la limite par continuité décroissante et conclure.

Le graphe est connexe non orienté, donc on peut montrer que la racine communique avec tout point de l'arbre.

\((Y_n)_n\) suit une marche aléatoire, donc une chaîne de Markov.

On pose \((S_n)_n\) une marche aléatoire similaire à \((Y_n)_n\), mais sans le cas particulier en \(0\).

On peut appliquer la Loi forte des grands nombres à \((S_n)_n\) pour avoir sa limite.

On a \(Y_n\geqslant S_n\), ce qui nous permet de conclure.

La distance à la racine tend vers \(+\infty\), donc la racine est transitoire.

On conclut par irréductibilité de la chaîne.

Cela se fait rapidement, en vérifiant que tous les états communiquent (ou pas).

\(u(x)\) peut être décomposé selon la valeur de \(X_1\), via la formule des probabilités totales.

Les deux temps d'arrêt sont toujours supérieurs à \(1\), donc on peut appliquer un shift sans changer leurs valeurs.

On conclut en appliquant la Propriété de Markov faible.

On développe \(u(x)=1\times u(x)\), avec \(1=p_x+r_x+q_x\).

On obtient la formule finale en simplifiant et en mettant tous les \(p_x\) et \(q_x\) du même côté.

On obtient une formule par récurrence, en faisant apparaître un produit.

On peut obtenir l'expression de \(u(x)\) en sommant les termes (puisque la somme est télescopique).

Il reste à calculer la constante, que l'on obtient en prenant \(x=b\).

C'est une chaîne de Markov connue.

Pour qu'elle soit irréductible, il faut que chaque document ait une probabilité non nulle d'être demandé.